
public class TestMain {

    public static void main(String[] args) {
        int n = 10;
        int[] data = SelectTest.getRandomSource(n);

        SelectTest.sort(data, n);

        // output
        for (int i = 0; i < data.length; i++) {
            System.out.printf("%4d", data[i]);
        }
        
//        NMatrix.initial();
//        NMatrix.calc();
//        NMatrix.output();
//        
//        NMatrix.outputResult(1, 5);
    }

}

class NMatrix {
    static int n = 5;
    static int[][] matrix = new int[n + 1][n + 1];
    static int[][] dest = new int[n+1][n+1];
    static int[] d = {2, 6, 3, 1, 3, 2};

    public static void initial() {
        for (int i = 1; i <= 5; i++) {
            matrix[i][i] = 0;
        }
    }

    public static void calc() {

        for (int diagonal = 1; diagonal < n; diagonal++) {
            for (int i = 1; i <= n-diagonal; i++) {
                int j = i + diagonal;
                
                matrix[i][j] = Integer.MAX_VALUE;

                for (int k = i; k < j; k++) {
                    int tmp = matrix[i][k] + matrix[k + 1][j] + d[i - 1] * d[k] * d[j];

                    if (tmp < matrix[i][j]) {
                        matrix[i][j] = tmp;
                        dest[i][j] = k;
                    }
                }
            }
        }
    }
    
    public static void outputResult(int i, int j) {
        
        if(i == j) {
            System.out.print("A" + i);
        } else {
            int k = dest[i][j];
            System.out.print("(");
            outputResult(i,k);
            outputResult(k+1,j);
            System.out.print(")");
        }
    }
    
    public static void output() {
        
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                System.out.printf("%4d", matrix[i][j]);
            }
            System.out.println();
        }
    }
}

class HeapTest {

    // s[1..n]
    public static int[] getRandomSource(int n) {
        int[] source = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            int tmp = (int) (Math.random() * 50);
            source[i] = tmp;
        }

        return source;
    }

    public static void createMaxHeap(int[] s, int n) {
        for (int i = n / 2; i >= 1; i--) {
            shift(s, i, n);
        }
    }

    public static void shift(int[] s, int i, int n) {

        int j = 2 * i;
        int tmp = s[i];

        while (j <= n) {
            if (j < n) {
                if (s[j] < s[j + 1]) {
                    j++;
                }
            }

            if (tmp < s[j]) {
                s[j / 2] = s[j];
                j *= 2;
            } else {
                break;
            }
        }

        s[j / 2] = tmp;
    }

    public static void sort(int[] s, int n) {

        createMaxHeap(s, n);

        int tmp = s[1];
        s[1] = s[n];
        s[n] = tmp;
        for (int i = n - 1; i >= 2; i--) {
            shift(s, 1, i);

            tmp = s[1];
            s[1] = s[i];
            s[i] = tmp;
        }
    }
}

class ShellTest {

    public static int[] getRandomSource(int n) {
        int[] source = new int[n];

        for (int i = 0; i < source.length; i++) {
            int tmp = (int) (Math.random() * 50);
            source[i] = tmp;
        }

        return source;
    }

    public static void sort(int[] s, int n) {

        for (int gap = n / 2; gap >= 1; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int tmp = s[i];
                int j = i - gap;

                while (j >= 0 && tmp < s[j]) {
                    s[j + gap] = s[j];
                    j -= gap;
                }

                s[j + gap] = tmp;
            }
        }
    }
}

class InsertTest {

    public static int[] getRandomSource(int n) {
        int[] source = new int[n];

        for (int i = 0; i < source.length; i++) {
            int tmp = (int) (Math.random() * 100);
            source[i] = tmp;
        }

        return source;
    }

    public static void sort(int[] s, int n) {

        for (int i = 1; i < n; i++) {
            int tmp = s[i];
            int j = i - 1;

            while (j >= 0 && tmp < s[j]) {
                s[j + 1] = s[j];
                j--;
            }

            s[j + 1] = tmp;
        }

    }
}

class SelectTest {

    public static int[] getRandomSource(int n) {
        int[] source = new int[n];

        for (int i = 0; i < source.length; i++) {
            int tmp = (int) (Math.random() * 100);
            source[i] = tmp;
        }

        return source;
    }

    public static void sort(int[] s, int n) {

        for (int i = 0; i < n; i++) {
            int j = i;
            for(int k=i+1;k<n;k++) {
                if(s[j] > s[k]) {
                    j=k;
                }
            }
            int tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
        }
    }
}

class QuickTest {

    public static int[] getRandomSource(int n) {
        int[] source = new int[n];

        for (int i = 0; i < source.length; i++) {
            int tmp = (int) (Math.random() * 100);
            source[i] = tmp;
        }

        return source;
    }

    public static void sort(int[] s, int left, int right, int n) {
        if (left <= right) {
            int k = partition(s, left, right, n);
            sort(s, left, k - 1, n);
            sort(s, k + 1, right, n);
        }
    }

    public static int partition(int[] s, int left, int right, int n) {
        int pivot = s[left];
        int i = left;
        int j = right + 1;

        while (true) {
            while (++i <= right && s[i] < pivot);
            while (--j >= left && s[j] > pivot);

            if (i < j) {
                int tmp = s[i];
                s[i] = s[j];
                s[j] = tmp;
            } else {
                break;
            }
        }

        s[left] = s[j];
        s[j] = pivot;

        return j;
    }
}